Arithmetic coding is a technology capable of reversibly compressing the quantity of information up to theoretical limits depending on the occurrence probability of information source symbols. Arithmetic coding is applied in the image coding fields in JPEG2000 standard (ISO/IEC15444), H.264/MPEG4-AVC standard (see, for example, non-patent document 1, hereinafter called H.264 standard), and others. For example, in H.264, Context Adaptive Binary Arithmetic Coding (CABAC) is applied, and coding of high efficiency is realized depending on the probability characteristic of syntax.
Context Adaptive Binary Arithmetic Coding in H.264 is explained by referring to FIG. 22. FIG. 22 is a diagram explaining a context adaptive binary arithmetic coding circuit.
A context adaptive binary arithmetic coding circuit 145 in FIG. 22 includes a binarizing circuit 130, a context calculating circuit 520, and an arithmetic coding circuit 140. The operation of the circuits is explained below.
The binarizing circuit 130 binarizes multivalued input data composed of conversion coefficient data, flags and other coding information. Binarization is performed by judging the syntax element showing the type of the input data from the control information, and using a method such as unary binarization and fixed-length binarization depending on the data probability characteristic as shown in Table 1.
TABLE 1Value of syntaxelementBin string0 (I N × N)01102110311104111105111110. . .binIdx012345
In the unary binarization shown in Table 1, binarization is performed by converting multivalued input data 0, 1, 2, 3, 4, 5, . . . into binary symbols (Bin string) 0, 10, 110, 1110, 11110, 111110, . . . . Binarized binary symbol sequences are input into the (binary) arithmetic coding circuit 140. Unary binarization is used for binarizing values of equal to or smaller than 14 in coeff_abs_level_minus1 showing the level of conversion coefficient.
The context calculating circuit 520 determines the value of context index (ctxIdx) used in coding of present 1 bit in the binary symbol sequence on the basis of the control information showing the syntax element according to Table 2 specified in the H.264 standard.
TABLE 2Slice typeSyntax elementS1IP, SPBslice_data( )mb_skip_flag11-1324-26mb_field_decoding_flag70-7270-7270-7270-72macroblock_layer( )mb_type 0-10 3-1014-2027-35transform_size_8×8_flagna399-401399-401399-401coded_block_pattern (luma)73-7673-7673-7673-76coded_block_pattern (chroma)77-8477-8477-8477-84mb_qp_delta60-6360-6360-6360-63mb_pred( )prev_intra4×4_pred_mode_flag68686868rem_intra4×4_pred_mode69696969prev_intra8×8_pred_mode_flagna686868rem_intra8×8_pred_modena696969intra_chroma_pred_mode64-6764-6764-6764-67mb_pred( ) andref_idx_I054-5954-59sub_mb_pred( )ref_idx_I154-59mvd_I0[ ][ ][0]40-4640-46mvd_I1[ ][ ][0]40-46mvd_I0[ ][ ][1]47-5347-53mvd_I1[ ][ ][1]47-53sub_mb_pred( )sub_mb_type21-2336-39residual_block_cabac( )coded_block_flag 85-104 85-104 85-104 85-104significant_coeff_flag[ ]105-165105-165105-165105-165277-337277-337277-337277-337402-416402-416402-416436-450436-450436-450last_significant_coeff_flag[ ]166-226166-226166-226166-226338-398338-398338-398338-398417-425417-425417-425451-459451-459451-459coeff_abs_level_minus1[ ]227-275227-275227-275227-275426-435426-435426-435
As known from Table 2, ctxIdx can receive 460 values from 0 to 459. In one syntax element, selection of ctxIdx varies depending on the slice type. For example, as ctxIdx of mb_field_decoding flag is 70-72 in slice type I, when determining the value of ctxIdx for the syntax element having a plurality of values of ctxIdx, it is determined by the operation of ctxIdx=ctxIdxOffset+ctxIdxInc, on the basis of the values of offset value ctxIdxOffset and increment value ctxIdxInc. ctxIdxOffset is an intrinsic value of syntax element shown in Table 3 (partly excerpted from the table of H.264 standard), and ctxIdxInc is uniformly determined from a plurality of values according to the rule determined in every syntax element (see the H.264 standard) In the case of mb_field_decoding_flag, ctxIdxOffset is 70, and any value from 0 to 2 is selected as ctxIdxInc depending on the condition.
The context calculating circuit 520 initializes and stores the occurrence probability information by calculation shown in FIG. 23 in every 460 values of ctxIdx at the time of start of slice. The occurrence probability information includes a set of MPS (valMPS) showing the symbol of higher occurrence probability of binary symbols 0 and 1, and pState (pStateIdx) showing the occurrence probability. The occurrence probability information corresponding to the determined value of ctxIdx is called the “context information”.
The context calculating circuit 520 generates the context information, and inputs into the arithmetic coding circuit 140. Thus, depending on the syntax element for arithmetic coding, the occurrence probability of the symbol to be entered in the arithmetic coding circuit 140, that is, the context information is changed over adaptively. As a result, in the binary symbol sequence dynamically changing in the occurrence probability of binary symbols, an optimum arithmetic coding is realized. Herein, the total bit length of output codes occurring at the time of process of multivalued input data in a specific section is called the “code amount.”
Concept of operation of the arithmetic coding circuit 140 is explained by referring to FIGS. 24A and 24B. Suppose binary sequences of {0, 0.0, 1} are supplied in the condition in which ctxIdx is constant at a certain value, and the occurrence probability obtained from the context information is 0.75 (0.11 in binary notation) for symbol 0, and 0.25 for symbol 1. In this case, as shown in FIG. 24 A, the present context information is expressed by MPS=0 showing the symbol of higher occurrence probability, and occurrence probability pState=0.11. Indeed, the actual pStateIdx is expressed by an index value in a range from 0 to 63, but a binary probability value is used herein for the sake of simplicity. The context information is updated by this binary arithmetic coding, and is returned to the context calculating circuit 520. In the context calculating circuit 520, the occurrence probability information of the corresponding ctxIdx is updated. This value is utilized again in the next coding process of the same ctxIdx.
Referring now to FIG. 24B, when a first input binary value “0” is entered, the section of [0, 1] is narrowed to the 0 side divided by probability 0.11, and becomes [0, 0.11]. When a second input “0” is entered, the section of [0, 0.11] is narrowed to [0, 0.1001]. Herein, 0.1001=0.11×0.11. Similarly, by a third input “0”, the section becomes [0, 0.011011]. When a fourth input “1” is entered, the section is narrowed to the 1 side, and the final section is narrowed to [0.01010001, 0.011011]. Of the values contained in this final section, the one having the shortest word length is the code word. That is, since 0.011 is contained in this section, the value “011” below the decimal point is an output binary sequence, and the four-bit input value is compressed to 3 bits.
In actual operation of the arithmetic coding circuit 140, since this section is handled by the finite word length, the output bit is established depending on the values of codILow and codIRange in which the left end value of the section is codILow (0.01010001, etc.), the section range is codIRange (0.00011011, etc.), and codIRange and codILow are shifted by 1 bit to the left, and the resolution of the section is enhanced, which is called renormalization. The actual 1-bit arithmetic coding process is executed according to the flowcharts shown in FIG. 25 and FIG. 26.
FIG. 25 shows the arithmetic coding process (820) of one binary (Bin) input, consisting of initialization of a variable (821), judging whether Bin is MPS or not (822), updating of codILow and codIRange if not MPS (823), judging the value of pStateIdx (824), inverting of MPS (825), updating of occurrence probability pStateIdx (826, 827), and renormalization (830). FIG. 25 shows the process of renormalization 830.
In FIG. 25 and FIG. 26, codIRange and codILow are internal state variables, and are initialized only at the beginning of a slice. Right after coding of the 4-bit input value shown in FIG. 24B, when coding an input value different in ctxIdx, only the context information is changed, and the values right after 4-bit coding are used for codIRange and codILow. In the case of arithmetic coding of conversion coefficient data, multivalued input data different in ctxIdx are continuously coded, such as significant_coeff_flag of luminance 64 coefficient, coeff_abs_level_minus1 of luminance 64 coefficient, significant_coeff_flag of color difference DC component, and coeff_abs_level_minus1 of color difference AC component, and the internal state is initialized only at the beginning of a slice; therefore, all syntax elements including them must be coded sequentially only within the slice, and cannot be processed in parallel.
On the other hand, in moving image coding, since input images having various characteristics are compressed at a specified bit rate, it is required to control the code amount by properly controlling the quantization parameter when coding each macro block. To enhance the precision of code amount control, it is general to code repeatedly by changing the parameters in the unit such as slice, frame, or GOP (group of pictures). The repeated coding includes two types of coding, provisional coding mainly for predicting the code amount, and final coding.
Conventional provisional coding methods are roughly classified into actual entropy coding same as in final coding, and substitute operation without performing entropy coding. The former method in the conventional coder generally uses the variable length coding for entropy coding. Recently, arithmetic coding is proposed for entropy coding. As mentioned above, arithmetic coding is coding process in bit unit, and it is sequential coding in a slice, and if arithmetic coding is applied in provisional coding, a tremendous code amount is required. Hence, in a circuit in which the real-time processing is required, it is quite difficult to apply arithmetic coding in provisional coding.
Accordingly, as provisional coding method when arithmetic coding is applied in final coding method, the latter method is proposed (substitute operation for entropy coding). For example, as disclosed in patent document 1, without performing arithmetic coding, the input binary symbol amount is used as the prediction value of output code amount, and the processing amount when selecting the optimum coding mode can be saved. Patent document 2 proposes a method of prediction by using functions.
Patent document 1: JP-A-2005-318296
Patent document 2: JP-A-2005-203905
Non-patent document 1: ISO/IEC14496-10 Advanced video coding for generic audiovisual services